#leetcode题目85：最大矩形
#难度：困难
#时间复杂度：O(n^2)
#空间复杂度：O(n)
#方法：栈,使用单调栈,前缀和

from typing import List
class Solution:
    def maximalRectangle(self, matrix: List[List[str]]) -> int:
        if not matrix:
            return 0
        m,n=len(matrix),len(matrix[0])
        pre=[0]*(n+1)
        res=0
        for i in range(m):
            for j in range(n):
                if matrix[i][j]=="1":
                    pre[j]+=1
                else:
                    pre[j]=0
            stk=[-1]
            for k,v in enumerate(pre):
                while stk and pre[stk[-1]] > v:
                    idx=stk.pop()
                    h=pre[idx]
                    w=k-stk[-1]-1
                    res=max(res,h*w)
                stk.append(k)
        return res

#测试数据
matrix=[["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
#预期输出：6
solution=Solution()
print(solution.maximalRectangle(matrix))

matrix=[["0","1"],["1","0"]]
#预期输出：1
solution=Solution()
print(solution.maximalRectangle(matrix))

        


